﻿#region Copyright and license information
// Copyright 2012 Richard Schneider
// 
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
// 
//     http://www.apache.org/licenses/LICENSE-2.0
// 
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#endregion

using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Text;
using NodaTime.Properties;
using NodaTime.Text;
using NodaTime.TimeZones;
using NodaTime.Utility;

namespace NodaTime
{
    /// <summary>
    ///   A rule or repeating pattern for recurring events.
    /// </summary>
    /// <remarks>
    /// <para>
    ///   This implementation is based on the "Recurrence Rule" (RRULE) in RFC 5545 - Internet Calendaring and Scheduling 
    ///   Core Object Specification (iCalendar).  The <see cref="Parse(string)"/> and <see cref="ToString"/> methods consume and produce a
    ///   conformant RRULE content line, respectively.
    /// </para>
    /// <para>
    ///   The <see cref="Enumerate"/> method is used to generate an ordered sequence of <see cref="ZonedDateTime"/> that
    ///   match the rule.  The sequence can, in theory, be infinite because each item is generated as needed,.  The length of the sequence can be
    ///   controlled with the <see cref="Count"/> or one of <see cref="UntilLocalDate"/>, <see cref="UntilLocalDateTime"/> or <see cref="Until"/>.
    ///   The Count and Until variants are mutually exclusive.
    /// </para>
    /// <para>
    ///   The By variants (<see cref="BySeconds"/>, <see cref="ByMinutes"/>, <see cref="ByHours"/>, <see cref="ByDays"/>,
    ///   <see cref="ByMonthDays"/>, <see cref="ByYearDays"/>, <see cref="ByWeeks"/>, <see cref="ByMonths"/>)
    ///   are used to expand or limit the dates generated by the <see cref="Frequency"/> and <see cref="Interval"/>.
    ///   Typically if the period of the By variant is less that the <see cref="Frequency"/>, the dates are expanded; otherwise they
    ///   are restricted.  For example, "FREQ=YEARLY;BYMONTH=1,2" increases the number of days within the yearly recurrence set from 1 to 2.
    ///   Whereas, "FREQ=DAILY;BYMONTH=1" reduces the number of recurrence instances from all days to all days in January.
    /// </para>
    /// </remarks>
    /// <example>
    ///   Enumerate every Friday 13th from a specified date, using the RFC 5545 RRULE syntax.
    ///   <code>
    /// public void FriggaTriskaidekaPhobia(ZonedDateTime now)
    /// {
    ///   var rule = RecurrenceRule.Parse("RRULE:FREQ=MONTHLY;BYDAY=FR;BYMONTHDAY=13");
    ///   foreach (var date in rule.Enumerate(now).Take(7))
    ///   {
    ///      Assert.AreEqual(IsoDayOfWeek.Friday, date.IsoDayOfWeek);
    ///   }
    /// }
    ///   </code>
    ///   <para>Using a C# initialiser.</para>
    ///   <code>
    ///    public void FriggaTriskaidekaPhobia(ZonedDateTime now)
    ///    {
    ///        var rule = new RecurrenceRule
    ///        {
    ///            Frequency = Frequency.Monthly,
    ///            ByDays = { new NthDay(IsoDayOfWeek.Friday) },
    ///            ByMonthDays = { 13 }
    ///        };
    ///        foreach (var date in rule.Enumerate(now).Take(7))
    ///        {
    ///            Assert.AreEqual(IsoDayOfWeek.Friday, date.IsoDayOfWeek);
    ///        }
    ///    }
    ///   </code>
    /// </example>
    public partial class RecurrenceRule
    {
        /// <summary>
        ///   The abbreviated day names specified by RFC 5545.
        /// </summary>
        /// <remarks>
        ///   These names (all upper case) are in the same order as <see cref="IsoDayOfWeek"/>. However, <b>IsoDayOfWeek</b> is 1-relative
        ///   and arrays are always 0-relative!
        /// </remarks>
        static internal readonly string[] Rfc5545WeekDayNames = { "MO", "TU", "WE", "TH", "FR", "SA", "SU" };

        // The date and/or time patterns for RRULE:UNTIL=xxx.
        static readonly LocalDatePattern Rfc5544DatePattern = LocalDatePattern.CreateWithInvariantCulture("yyyyMMdd");
        static readonly LocalDateTimePattern Rfc5545DateTimePattern = LocalDateTimePattern.CreateWithInvariantCulture("yyyyMMdd'T'HHmmss");
        static readonly InstantPattern Rfc5545InstantPattern = InstantPattern.CreateWithInvariantCulture("yyyyMMdd'T'HHmmss'Z'");

        struct ValidationRule
        {
            public readonly Func<RecurrenceRule, CalendarSystem, bool> Rule;
            public readonly string Message;

            public ValidationRule(Func<RecurrenceRule, CalendarSystem, bool> rule, string message)
            {
                Rule = rule;
                Message = message;
            }
        }

        static readonly ValidationRule[] ValidationRules = 
        {
            new ValidationRule((r,c) => r.Frequency != Frequency.NotDefined, "The Frequency must be defined."),   
            new ValidationRule((r,c) => r.Interval > 0, "The Interval must be positive."),   
            new ValidationRule((r,c) => r.Count == 0 || !(r.Until.HasValue || r.UntilLocalDate.HasValue || r.UntilLocalDateTime.HasValue), 
                "The Count and Until variants are mutually exclusive."),  
            new ValidationRule((r,c) => (r.Until.HasValue ? 1 : 0) + (r.UntilLocalDate.HasValue ? 1 : 0) + (r.UntilLocalDateTime.HasValue ? 1 : 0) < 2,
                "The Until variants are mutually exclusive."),
            new ValidationRule((r,c) => r.BySeconds.All(s => 0 <= s && s <= NodaConstants.SecondsPerMinute), "Invalid second value."),   
            new ValidationRule((r,c) => r.ByMinutes.All(m => 0 <= m && m < NodaConstants.MinutesPerHour), "Invalid minute value."),   
            new ValidationRule((r,c) => r.ByHours.All(h => 0 <= h && h < NodaConstants.HoursPerStandardDay), "Invalid hour value."),   
            new ValidationRule((r,c) => r.ByDays.All(d => Enum.IsDefined(typeof(IsoDayOfWeek), d.DayOfWeek)), "Invalid day of week value."), // Enums are evil!
            new ValidationRule((r,c) => r.ByDays.All(d => d.DayOfWeek != IsoDayOfWeek.None), "Invalid day of week value."),
            new ValidationRule((r,c) => Enum.IsDefined(typeof(IsoDayOfWeek), r.WeekStartDay), "Invalid day of week value."), // Enums are evil!
            new ValidationRule((r,c) => r.WeekStartDay != IsoDayOfWeek.None, "Invalid day of week value."),
            new ValidationRule(
                (r,c) => r.ByDays.All(d => d.Occurrence == 0 || r.Frequency == Frequency.Monthly || r.Frequency == Frequency.Yearly), 
                "The BYDAY rule part MUST NOT be specified with a numeric value when the FREQ rule part is not set to MONTHLY or YEARLY."),   
            new ValidationRule(
                (r,c) => r.ByDays.All(d => d.Occurrence == 0 || r.Frequency != Frequency.Yearly || r.ByWeeks.Count == 0), 
                "The BYDAY rule part MUST NOT be specified with a numeric value with the FREQ rule part set to YEARLY when the BYWEEKNO rule part is specified."),
            new ValidationRule((r,c) => r.ByMonths.All(m => m <= c.GetMaxMonth()), "Invalid month value."),
            new ValidationRule((r,c) => r.ByMonthDays.All(m => Math.Abs(m) <= c.GetMaxDaysInMonth()), "Invalid month day value."),
            new ValidationRule((r,c) => r.ByYearDays.All(d => Math.Abs(d) <= c.GetDaysInYearMax()), "Invalid year day value."),
            new ValidationRule((r,c) => r.BySetPositions.All(x => Math.Abs(x) <= c.GetDaysInYearMax()), "Invalid set position value."),
            // TODO: need a CalendarSystem.GetMaxWeeksInYear().  Hardwired for ISO calendar.
            new ValidationRule((r,c) => r.ByWeeks.All(w => Math.Abs(w) <= 53), "Invalid year day value."),
            new ValidationRule(
                (r,c) => r.ByMonthDays.Count == 0 || r.Frequency != Frequency.Weekly,
                "The BYMONTHDAY rule part MUST NOT be specified when the FREQ rule part is set to WEEKLY."),
            new ValidationRule(
                (r,c) => r.ByWeeks.Count == 0 || r.Frequency == Frequency.Yearly,
                "The BYWEEKNO rule part MUST NOT be specified when the FREQ rule part is set to anything other than YEARLY."),
            new ValidationRule(
                (r,c) => r.ByYearDays.Count == 0 || !(r.Frequency == Frequency.Daily || r.Frequency == Frequency.Weekly || r.Frequency == Frequency.Monthly),
                "The BYYEARDAY rule part MUST NOT be specified when the FREQ rule part is set to DAILY, WEEKLY, or MONTHLY."),
            new ValidationRule(
                (r,c) => r.BySetPositions.Count == 0 || r.BySeconds.Count > 0 || r.ByMinutes.Count > 0 || r.ByHours.Count > 0
                    || r.ByDays.Count > 0 || r.ByMonthDays.Count > 0 || r.ByYearDays.Count > 0 || r.ByMonths.Count > 0
                    || r.ByWeeks.Count > 0,
                "THE BYSETPOS rule part MUST only be used in conjunction with another BY rule part."),
            new ValidationRule((r,c) => r.BySetPositions.All(v => v != 0), "Zero is not valid value for BYSETPOS."),
            new ValidationRule((r,c) => r.ByMonthDays.All(v => v != 0), "Zero is not valid value for BYMONTHDAY."),
            new ValidationRule((r,c) => r.ByYearDays.All(v => v != 0), "Zero is not valid value for BYYEARDAY."),
            new ValidationRule((r,c) => r.ByWeeks.All(v => v != 0), "Zero is not valid value for BYWEEKNO."),
            new ValidationRule((r,c) => r.ByMonths.All(v => v > 0), "Invalid BYMONTH value."),
        };

        /// <summary>
        ///   Creates a new instance of the <see cref="RecurrenceRule"/> class.
        /// </summary>
        public RecurrenceRule()
        {
            Interval = 1;
            WeekStartDay = IsoDayOfWeek.Monday;
            BySeconds = new List<int>();
            ByMinutes = new List<int>();
            ByHours = new List<int>();
            ByMonths = new List<int>();
            ByWeeks = new List<int>();
            ByMonthDays = new List<int>();
            ByYearDays = new List<int>();
            ByDays = new List<NthDay>();
            BySetPositions = new List<int>();
        }

        /// <summary>
        ///   Determines how the rule repeats (daily, monthly, etc).
        /// </summary>
        /// <value>
        ///   One of the <see cref="NodaTime.Frequency"/> enumerated values.
        /// </value>
        public Frequency Frequency { get; set; }

        /// <summary>
        ///   Determines how often the rule repeats.
        /// </summary>
        /// <value>
        ///   A positive <see cref="int"/> defaulting to 1.
        /// </value>
        /// <example>
        ///   A rule that repeats every eight days.
        ///   <code>
        ///   var everyEightDays = new RecurrencyRule { Frequency = Frequency.Daily, Interval = 8 }; 
        ///   </code>
        /// </example>
        public int Interval { get; set; }

        /// <summary>
        ///   Limits the sequence returned by <see cref="Enumerate"/> to a specific length.
        /// </summary>
        /// <value>
        ///   A non-negative <see cref="int"/>.  A zero value implies unlimited length; which is the default.
        /// </value>
        /// <remarks>
        ///   The <b>Count</b> property is equivalent to the "COUNT" part rule of RFC 5545, for example <c>RRULE:FREQ=YEARLY;COUNT=2</c>.
        /// <para>
        ///   The LINQ equivalent is <c>RecurreneRule.Parse("RRULE:FREQ=YEARLY").Enumerate(start).Take(2)</c>.
        /// </para>
        /// </remarks>
        /// <seealso cref="Until"/>
        public int Count { get; set; }

        /// <summary>
        ///   Limits the sequence returned by <see cref="Enumerate"/> to dates less than or equal (inclusive) to the
        ///   specified <see cref="LocalDate"/>. 
        /// </summary>
        /// <remarks>
        ///   The <b>UntilLocalDate</b> property is equivalent to the "UNTIL" part rule of RFC 5545, for example <c>RRULE:FREQ=YEARLY;UNTIL=20121031</c>.
        /// <para>
        ///   The <see cref="Until"/> property is preferable to avoid any <see cref="SkippedTimeException">skipped</see> 
        ///   or <see cref="AmbiguousTimeException">ambiguous</see> dates.
        /// </para>
        /// <para>
        ///   <see cref="UntilLocalDate"/>, <see cref="UntilLocalDateTime"/> are <see cref="Until"/> mutually exclusive.
        /// </para>
        /// </remarks>
        /// <seealso cref="Until"/>
        /// <seealso cref="Count"/>
        public LocalDate? UntilLocalDate { get; set; }

        /// <summary>
        ///   Limits the sequence returned by <see cref="Enumerate"/> to date-times less than or equal (inclusive) to the
        ///   specified <see cref="LocalDateTime"/>. 
        /// </summary>
        /// <remarks>
        ///   The <b>UntilLocalDateTime</b> property is equivalent to the "UNTIL" part rule of RFC 5545, for example <c>RRULE:FREQ=YEARLY;UNTIL=20121031T210000</c>.
        /// <para>
        ///   The <see cref="Until"/> property is preferable to avoid any <see cref="SkippedTimeException">skipped</see> 
        ///   or <see cref="AmbiguousTimeException">ambiguous</see> dates.
        /// </para>
        /// <para>
        ///   <see cref="UntilLocalDate"/>, <see cref="UntilLocalDateTime"/> are <see cref="Until"/> mutually exclusive.
        /// </para>
        /// </remarks>
        /// <seealso cref="Until"/>
        /// <seealso cref="Count"/>
        public LocalDateTime? UntilLocalDateTime { get; set; }

        /// <summary>
        ///   Limits the sequence returned by <see cref="Enumerate"/> to date-times less than or equal (inclusive) to the
        ///   specified <see cref="Instant"/>. 
        /// </summary>
        /// <remarks>
        ///   The <b>Until</b> property is equivalent to the "UNTIL" part rule of RFC 5545, for example <c>RRULE:FREQ=YEARLY;UNTIL=20121031T210000Z</c>.
        /// <para>
        ///   The LINQ equivalent is <c>RecurreneRule.Parse("RRULE:FREQ=YEARLY").Enumerate(start).TakeWhile(d => d &lt;= until)</c>.
        /// </para>
        /// <para>
        ///   <see cref="UntilLocalDate"/>, <see cref="UntilLocalDateTime"/> are <see cref="Until"/> mutually exclusive.
        /// </para>
        /// </remarks>
        /// <seealso cref="Count"/>
        public Instant? Until { get; set; }

        /// <summary>
        ///   The start day of a week.
        /// </summary>
        /// <value>
        ///   One of the <see cref="IsoDayOfWeek"/> enumeration values.  The default is <see cref="IsoDayOfWeek.Monday"/>,
        ///   which is the ISO-8601 standard. 
        /// </value>
        public IsoDayOfWeek WeekStartDay { get; set; }

        /// <summary>
        ///   The week numbers for this rule.
        /// </summary>
        /// <remarks>
        ///   A positive number specifies a week from the beginning of the year.  A negative number specifies a week from
        ///   the end of the year; e.g. 1 is the first week of year and -1 is the last week of the year.
        /// </remarks>
        public List<int> ByWeeks { get; private set; }

        /// <summary>
        ///   The month numbers for this rule.
        /// </summary>
        /// <remarks>
        ///   Only positive numbers are allowed.
        /// </remarks>
        public List<int> ByMonths { get; private set; }

        /// <summary>
        ///   A list of days for this rule.
        /// </summary>
        public List<NthDay> ByDays { get; private set; }

        /// <summary>
        ///   A list of month days for this rule.
        /// </summary>
        /// <remarks>
        ///   A positive number specifies the day from the beginning of the month.  A negative number specifies the day
        ///   from the end of the month; e.g. 1 is the first day of month and -1 is the last day of the month.
        /// </remarks>
        public List<int> ByMonthDays { get; private set; }

        /// <summary>
        ///   A list of year days for this rule.
        /// </summary>
        /// <remarks>
        ///   A positive number specifies the day from the beginning of the year.  A negative number specifies the day
        ///   from the end of the year; e.g. 1 is the first day of year and -1 is the last day of the year.
        /// </remarks>
        public List<int> ByYearDays { get; private set; }

        /// <summary>
        ///   The seconds for this rule.
        /// </summary>
        /// <remarks>
        ///   Only positive numbers are allowed.
        /// </remarks>
        public List<int> BySeconds { get; private set; }

        /// <summary>
        ///   The minutes for this rule.
        /// </summary>
        /// <remarks>
        ///   Only positive numbers are allowed.
        /// </remarks>
        public List<int> ByMinutes { get; private set; }

        /// <summary>
        ///   The hours for this rule.
        /// </summary>
        /// <remarks>
        ///   Only positive numbers are allowed.
        /// </remarks>
        public List<int> ByHours { get; private set; }

        /// <summary>
        ///   TODO: BySetPosition documentation.
        /// </summary>
        public List<int> BySetPositions { get; private set; }

        /// <summary>
        ///   Determines if the <see cref="RecurrenceRule"/> properties are valid for the specified <see cref="CalendarSystem"/>.
        /// </summary>
        /// <param name="calendar">
        ///   The <see cref="Calendar"/> used for validation.
        /// </param>
        /// <param name="validationHandler">
        ///   The <see cref="Action"/> that receives any validation failure messages; or <b>null</b>.
        /// </param>
        /// <returns>
        ///   <b>true</b> if the <see cref="RecurrenceRule"/> is valid; otherwise, <b>false</b>.
        /// </returns>
        /// <exception cref="ArgumentNullException">
        ///   <paramref name="calendar"/> is <b>null</b>.
        /// </exception>
        /// <remarks>
        ///   Certain validation rules, such as <see cref="ByMonths"/>, require a <see cref="Calendar"/> to determined the bounds.
        /// </remarks>
        /// <example>
        ///   The following throws an exception on the first validation rule that fails. The failure message is "The Frequency must be defined.".
        ///   <code>
        ///     var rule = new RecurrenceRule();
        ///     rule.Validate(CalendarSystem.Iso, failure => { throw new Exception(failure); });
        ///   </code>
        /// </example>
        public bool Validate(CalendarSystem calendar, Action<string> validationHandler)
        {
            Preconditions.CheckNotNull(calendar, "calendar");

            bool isValid = true;
            foreach (var failure in ValidationRules.Where(v => !v.Rule(this, calendar)))
            {
                isValid = false;
                if (validationHandler != null)
                    validationHandler(failure.Message);
            }
            return isValid;
        }

        /// <summary>
        ///   Returns an enumerable sequence of date times that match the rule from the
        ///   specified start <see cref="ZonedDateTime"/>.
        /// </summary>
        /// <param name="start">
        ///   The start <see cref="ZonedDateTime"/> for this rule.  The behaviour is undefined if the
        ///   start part does not fit the pattern.
        /// </param>
        /// <returns>
        ///   An  <see cref="IEnumerable{ZonedDateTime}">enumerable</see> sequence of <seealso cref="ZonedDateTime"/>
        ///   that is <see cref="ZonedDateTime.CompareTo">ordered</see> and matches
        ///   rule for the <paramref name="start"/> date time.
        /// </returns>
        /// <exception cref="InvalidOperationException">
        ///   If any property of this rule <see cref="Validate">is not valid</see>.
        /// </exception>
        /// <exception cref="ArgumentException">
        ///   The <see cref="CalendarSystem"/> of <paramref name="start"/> does not equal the <see cref="UntilLocalDateTime"/> 
        ///   or <see cref="UntilLocalDate"/> calendar system.
        /// </exception>
        /// <remarks>
        ///   This method is implemented by using deferred execution. The immediate return value is an object that stores all the information that is required 
        ///   to perform the action. The query represented by this method is not executed until the object is enumerated either by calling its GetEnumerator method 
        ///   directly or by using <c>foreach</c>.
        /// <para>
        ///  The sequence can, in theory, be infinite because each item is generated as needed,.  The length of the sequence can be
        ///   controlled with the <see cref="Count"/> or <see cref="Until"/> properties;  or by using an <see cref="IEnumerable{T}"/> limiter.
        /// </para>
        /// </remarks>
        /// <example>
        ///   <code>
        /// public void FriggaTriskaidekaPhobia(ZonedDateTime now)
        /// {
        ///   var rule = RecurrenceRule.Parse("RRULE:FREQ=MONTHLY;BYDAY=FR;BYMONTHDAY=13");
        ///   foreach (var date in rule.Enumerate(now).Take(7))
        ///   {
        ///      Assert.AreEqual(IsoDayOfWeek.Friday, date.IsoDayOfWeek);
        ///   }
        /// }
        ///   </code>
        /// </example>
        public IEnumerable<ZonedDateTime> Enumerate(ZonedDateTime start)
        {
            // Is the recurrence rule valid? 
            Validate(start.LocalDateTime.Calendar, failure => { throw new InvalidOperationException(failure); });

            // Determine an until instant.
            Instant? until = null;
            if (Until.HasValue)
                until = Until.Value;
            else if (UntilLocalDateTime.HasValue)
            {
                if (start.LocalDateTime.Calendar != UntilLocalDateTime.Value.Calendar)
                    throw new ArgumentException(Messages.RecurrenceRule_Instances_The_start_and_until_calendars_are_not_the_same_, "start");

                until = start.Zone.AtStrictly(UntilLocalDateTime.Value).ToInstant();
            }
            else if (UntilLocalDate.HasValue)
            {
                if (start.LocalDateTime.Calendar != UntilLocalDate.Value.Calendar)
                    throw new ArgumentException(Messages.RecurrenceRule_Instances_The_start_and_until_calendars_are_not_the_same_, "start");

                until = start.Zone.AtStrictly(UntilLocalDate.Value.AtMidnight()).ToInstant();
            }

            // TODO: How do we handle patterns that do not generate any instances? The follow pattern
            //   does not return: "RRULE:FREQ=YEARLY;INTERVAL=4;BYYEARDAY=366" start="20000101"

            var dates = GenerateInstance(start.LocalDateTime)           // Generate the instances (dates) based on frequency and interval.
                .SelectMany(d => GenerateResultantSet(d, start));       // limit/expand each instance using the By variants.

            // Zoned date-times are now partially ordered.  An ambiguous (leaving daylight time) LocalDateTime will have two entries and
            // be out of sequence.  We can do a partial date-time sort that is grouped by the date.  This way we don't have to have all
            // the instances of the result!
            dates = PartialSort(dates);

            dates = OrderedDistinct(dates);                   


            // Only take the first Count instances.
            if (Count > 0)
                dates = dates.Take(Count);

            // Only take instances <= Until variant  Note: instances are sorted ascending.
            if (until.HasValue)
                dates = dates.TakeWhile(d => d.ToInstant() <= until.Value);

            return dates;
        }

        /// <summary>
        ///   The RFC 5545 representation of the <see cref="RecurrenceRule"/>.
        /// </summary>
        /// <remarks>
        ///   The returned value is culturally invariant and can be used for "round tripping".
        /// </remarks>
        public override string ToString()
        {
            var s = new StringBuilder("RRULE:");

            // To ensure backward compatibility with applications that pre-date this revision of iCalendar 
            // the FREQ rule part MUST be the first rule part specified in a RECUR value.
            s.AppendFormat("FREQ={0}", Frequency.ToString().ToUpperInvariant());

            if (Interval != 1)
                s.AppendFormat(";INTERVAL={0}", Interval);
            
            // COUNT and UNTIL are mutually exclusive.
            if (Count != 0)
                s.AppendFormat(";COUNT={0}", Count);
            else if (Until.HasValue)
                s.AppendFormat(";UNTIL={0}", Rfc5545InstantPattern.Format(Until.Value));
            else if (UntilLocalDateTime.HasValue)
                s.AppendFormat(";UNTIL={0}", Rfc5545DateTimePattern.Format(UntilLocalDateTime.Value));
            else if (UntilLocalDate.HasValue)
                s.AppendFormat(";UNTIL={0}", Rfc5544DatePattern.Format(UntilLocalDate.Value));

            // BYxxx rule parts.
            if (BySeconds.Count > 0)
            {
                s.Append(";BYSECOND=");
                s.Append(string.Join(",", BySeconds.Select(v => v.ToString(CultureInfo.InvariantCulture)).ToArray()));
            }
            if (ByMinutes.Count > 0)
            {
                s.Append(";BYMINUTE=");
                s.Append(string.Join(",", ByMinutes.Select(v => v.ToString(CultureInfo.InvariantCulture)).ToArray()));
            }
            if (ByHours.Count > 0)
            {
                s.Append(";BYHOUR=");
                s.Append(string.Join(",", ByHours.Select(v => v.ToString(CultureInfo.InvariantCulture)).ToArray()));
            }
            if (ByDays.Count > 0)
            {
                s.Append(";BYDAY=");
                s.Append(string.Join(",", ByDays.Select(v => v.ToString()).ToArray()));
            }
            if (ByMonthDays.Count > 0)
            {
                s.Append(";BYMONTHDAY=");
                s.Append(string.Join(",", ByMonthDays.Select(v => v.ToString(CultureInfo.InvariantCulture)).ToArray()));
            }
            if (ByYearDays.Count > 0)
            {
                s.Append(";BYYEARDAY=");
                s.Append(string.Join(",", ByYearDays.Select(v => v.ToString(CultureInfo.InvariantCulture)).ToArray()));
            }
            if (ByWeeks.Count > 0)
            {
                s.Append(";BYWEEKNO=");
                s.Append(string.Join(",", ByWeeks.Select(v => v.ToString(CultureInfo.InvariantCulture)).ToArray()));
            }
            if (ByMonths.Count > 0)
            {
                s.Append(";BYMONTH=");
                s.Append(string.Join(",", ByMonths.Select(v => v.ToString(CultureInfo.InvariantCulture)).ToArray()));
            }
            if (WeekStartDay != IsoDayOfWeek.Monday)
            {
                s.Append(";WKST=");
                s.Append(Rfc5545WeekDayNames[(int) WeekStartDay - 1]);
            }
            if (BySetPositions.Count > 0)
            {
                s.Append(";BYSETPOS=");
                s.Append(string.Join(",", BySetPositions.Select(v => v.ToString(CultureInfo.InvariantCulture)).ToArray()));
            }

            return s.ToString();
        }

        /// <summary>
        ///   Create a new <see cref="RecurrenceRule"/> from the specified RFC 5544 "RRULE" <see cref="string"/>.
        /// </summary>
        /// <param name="s">
        ///   A RFC 5545 "RRULE" <see cref="string"/>.
        /// </param>
        /// <returns>
        ///   A <see cref="RecurrenceRule"/>.
        /// </returns>
        /// <example>
        ///   <code>
        ///   var rrule = "RRULE:FREQ=MONTHLY;BYDAY=FR;BYMONTHDAY=13";
        ///   var start = ...;
        ///   foreach (var instance in ReccurenceRule.Parse(rrule).Enumerate(start))
        ///   {
        ///       Console.WriteLine(instance);
        ///   }
        ///   </code>
        /// </example>
        public static RecurrenceRule Parse(string s)
        {
            return Parse(new RecurrenceRule(), s);
        }

        static RecurrenceRule Parse(RecurrenceRule rule, string s)
        {
            var reader = new Text.InternetCalendarReader(new StringReader(s));

            reader.Match("rrule");
            reader.Match(':');

            // Process the rule parts.
            var processedParts = new List<string>();
            do
            {
                var partName = reader.ReadName();
                if (partName == null)
                    break;
                reader.Match('=');

                // Individual rule parts must only be specified once.
                var name = partName.ToLowerInvariant();
                if (processedParts.Contains(name))
                    throw new FormatException(string.Format("The rule part '{0}' is already specified.", partName));
                processedParts.Add(name);

                switch (name)
                {
                    case "interval":
                        rule.Interval = reader.ReadParameterValue<int>();
                        break;
                    case "count":
                        rule.Count = reader.ReadParameterValue<int>();
                        break;
                    case "freq":
                        var freq = reader.ReadParameterValue();
                        try  // Enum.TryParse is not available in .Net 3.5!
                        {
                            rule.Frequency = (Frequency)Enum.Parse(typeof(Frequency), freq, true);
                        }
                        catch (Exception)
                        {
                            throw new FormatException(string.Format("The frequency value '{0}' is invalid.", freq));
                        }
                        break;
                    case "until":
                    {
                        var until = reader.ReadParameterValue();
                        Instant instant;
                        LocalDateTime dateTime;
                        LocalDate date;
                        if (Rfc5545InstantPattern.Parse(until).TryGetValue(default(Instant), out instant))
                            rule.Until = instant;
                        else if (Rfc5545DateTimePattern.Parse(until).TryGetValue(default(LocalDateTime), out dateTime))
                            rule.UntilLocalDateTime = dateTime;
                        else if (Rfc5544DatePattern.Parse(until).TryGetValue(default(LocalDate), out date))
                            rule.UntilLocalDate = date;
                        else
                            throw new FormatException(string.Format("Expected a date, date time, or date time UTC value not '{0}'", until));
                        break;
                    }
                    case "bymonth":
                        rule.ByMonths.AddRange(reader.ReadParameterValues<int>());
                        break;
                    case "byhour":
                        rule.ByHours.AddRange(reader.ReadParameterValues<int>());
                        break;
                    case "byminute":
                        rule.ByMinutes.AddRange(reader.ReadParameterValues<int>());
                        break;
                    case "bysecond":
                        rule.BySeconds.AddRange(reader.ReadParameterValues<int>());
                        break;
                    case "bysetpos":
                        rule.BySetPositions.AddRange(reader.ReadParameterValues<int>());
                        break;
                    case "byweekno":
                        rule.ByWeeks.AddRange(reader.ReadParameterValues<int>());
                        break;
                    case "bymonthday":
                        rule.ByMonthDays.AddRange(reader.ReadParameterValues<int>());
                        break;
                    case "byyearday":
                        rule.ByYearDays.AddRange(reader.ReadParameterValues<int>());
                        break;
                    case "byday":
                        var bydays = reader.ReadParameterValues();
                        rule.ByDays.AddRange(bydays.Select(day => new NthDay(day)));
                        break;
                    case "wkst":
                        var dayName = reader.ReadParameterValue().ToUpperInvariant();
                        var weekStartDay = Array.IndexOf(Rfc5545WeekDayNames, dayName);
                        if (weekStartDay < 0)
                            throw new FormatException(string.Format("Unknown WKST value '{0}'.", dayName));
                        rule.WeekStartDay = (IsoDayOfWeek)(weekStartDay + 1);
                        break;
                    default:
                        if (partName.StartsWith("X-") || partName.StartsWith("x-"))
                            reader.ReadParameterValues().All(v => true);
                        else
                            throw new FormatException(string.Format("Unknown RRULE parameter '{0}'.", partName));
                        break;
                }
            } while (reader.Maybe(';')); // repeat if another parameter is present.

            return rule;
        }

        IEnumerable<LocalDateTime> GenerateInstance(LocalDateTime start)
        {
            // Determine the maximum period we can increment each instance by.
            Period period;
            switch (Frequency)
            {
                case Frequency.Secondly: period = Period.FromSeconds(Interval); break;
                case Frequency.Minutely: period = Period.FromMinutes(Interval); break;
                case Frequency.Hourly: period = Period.FromHours(Interval); break;
                case Frequency.Daily: period = Period.FromDays(Interval); break;
                case Frequency.Weekly: period = Period.FromWeeks(Interval); break;
                case Frequency.Monthly: period = Period.FromMonths(Interval); break;
                case Frequency.Yearly: period = Period.FromYears(Interval); break;
                default:
                    throw new InvalidOperationException("The Frequency value is invalid.");
            }

            // Yield each instance.
            LocalDateTime instance = start;
            while (true)
            {
                yield return instance;
                instance = instance + period;
            }
        }

        /// <summary>
        ///   Returns an ordered sequence (not distinct) for the specified instant <see cref="LocalDateTime"/> that match
        ///   the ByXXX variants.
        /// </summary>
        /// <param name="date">
        ///   A <see cref="LocalDateTime"/> based on the <see cref="Frequency"/> and <see cref="Interval"/>.
        ///   See <see cref="GenerateInstance"/>.
        /// </param>
        /// <param name="start">
        ///   A <see cref="ZonedDateTime"/>.  Any generated date less than this will be ignored.
        /// </param>
        /// <returns></returns>
        /// <remarks>
        ///   <b>GenerateResultantSet</b> applies the ByXXX variants to the <paramref name="date"/> and returns
        ///   an order sequence of <see cref="LocalDateTime"/>; duplicate <see cref="LocalDateTime"/> may exist.
        /// </remarks>
        /// <seealso cref="GenerateInstance"/>
        IEnumerable<ZonedDateTime> GenerateResultantSet(LocalDateTime date, ZonedDateTime start)
        {
            IEnumerable<LocalDateTime> dates = new LocalDateTime[] { date };

            // The order of execution is specified by RFC 5545.
            dates = GenerateByMonth(dates);
            dates = GenerateByWeek(dates);
            dates = GenerateByYearDay(dates);
            dates = GenerateByMonthDay(dates);
            dates = GenerateByDay(dates);
            dates = GenerateByHour(dates);
            dates = GenerateByMinute(dates);
            dates = GenerateBySecond(dates);
            dates = LimitBySetPosition(dates);

            // The date sequence must be an ordered by ZonedDateTime.
            return dates
                .SelectMany(d => ResolveLocalDateTime(start.Zone.MapLocal(d)))
                .OrderBy(d => d)
                .SkipWhile(d => d < start);
        }

        IEnumerable<LocalDateTime> GenerateBySecond(IEnumerable<LocalDateTime> dates)
        {
            if (BySeconds.Count == 0)
                return dates;

            if (Frequency <= Frequency.Secondly)
                return dates.Where(d => BySeconds.Contains(d.Second));

            return dates.SelectMany(d => BySeconds.Select(s => d.PlusSeconds(s - d.Second)));
        }

        IEnumerable<LocalDateTime> GenerateByMinute(IEnumerable<LocalDateTime> dates)
        {
            if (ByMinutes.Count == 0)
                return dates;

            if (Frequency <= Frequency.Minutely)
                return dates.Where(d => ByMinutes.Contains(d.Minute));

            return dates.SelectMany(d => ByMinutes.Select(m => d.PlusMinutes(m - d.Minute)));
        }

        IEnumerable<LocalDateTime> GenerateByHour(IEnumerable<LocalDateTime> dates)
        {
            if (ByHours.Count == 0)
                return dates;

            if (Frequency <= Frequency.Hourly)
                return dates.Where(d => ByHours.Contains(d.Hour));

            return dates.SelectMany(d => ByHours.Select(h => d.PlusHours(h - d.Hour)));
        }

        IEnumerable<LocalDateTime> GenerateByMonth(IEnumerable<LocalDateTime> dates)
        {
            if (ByMonths.Count == 0)
                return dates;

            if (Frequency <= Frequency.Monthly)
                return dates.Where(d => ByMonths.Contains(d.Month));

            return dates.SelectMany(d => ByMonths.Select(m => d.PlusMonths(m - d.Month)));
        }

        IEnumerable<LocalDateTime> GenerateByWeek(IEnumerable<LocalDateTime> dates)
        {
            if (ByWeeks.Count == 0)
                return dates;

            if (Frequency == Frequency.Yearly)
                return dates.SelectMany(d =>
                   AbsoluteWeeks(ByWeeks, d)
                   .Select(w => d.PlusWeeks(w - d.WeekOfWeekYear))
                   .SelectMany(AllDaysInWeek)
                   );

            throw new InvalidOperationException("ByWeek for " + Frequency.ToString());
        }

        IEnumerable<LocalDateTime> GenerateByYearDay(IEnumerable<LocalDateTime> dates)
        {
            if (ByYearDays.Count == 0)
                return dates;

            // NOTE: RFC 5545, does not state that the BYWEEKNO limit BYYEARDAY in the limit/expand
            // table.  However, most implementation do this.  
            // See also http://www.imc.org/ietf-calendar/mail-archive/msg06788.html
            if (Frequency <= Frequency.Hourly
               || Frequency == Frequency.Yearly && ByWeeks.Count > 0)
                return dates.Where(d => AbsoluteYearDays(ByYearDays, d).Contains(d.DayOfYear));

            if (Frequency != Frequency.Yearly)
                throw new InvalidOperationException("ByYearDay for " + Frequency.ToString());

            return dates.SelectMany(d => AbsoluteYearDays(ByYearDays, d).Select(yd => d.PlusDays(yd - d.DayOfYear)));
        }

        IEnumerable<LocalDateTime> GenerateByMonthDay(IEnumerable<LocalDateTime> dates)
        {
            if (ByMonthDays.Count == 0)
                return dates;

            // NOTE: RFC 5545, does not state that the BYWEEKNO and BYYEARDAY limit ByMonthDay in the limit/expand
            // table.  However, most implementation do this.  
            // See also http://www.imc.org/ietf-calendar/mail-archive/msg06788.html
            if (Frequency <= Frequency.Daily
               || Frequency == Frequency.Yearly && ByWeeks.Count > 0
               || Frequency == Frequency.Yearly && ByYearDays.Count > 0)
                return dates.Where(d => AbsoluteMonthDays(ByMonthDays, d).Contains(d.Day));

            if (Frequency == Frequency.Weekly)
                throw new InvalidOperationException("ByMonthDay for " + Frequency.ToString());

            return dates.SelectMany(d => AbsoluteMonthDays(ByMonthDays, d).Select(md => d.PlusDays(md - d.Day)));
        }

        IEnumerable<LocalDateTime> GenerateByDay(IEnumerable<LocalDateTime> dates)
        {
            if (ByDays.Count == 0)
                return dates;

            if (Frequency <= Frequency.Daily ||
               (Frequency == Frequency.Monthly && ByMonthDays.Count > 0) ||
               (Frequency == Frequency.Yearly && ByWeeks.Count > 0) || // Not in spec, but appears to be correct.
               (Frequency == Frequency.Yearly && ByMonthDays.Count > 0) ||
               (Frequency == Frequency.Yearly && ByYearDays.Count > 0))
                return dates.Where(d => ByDaysContains(d));

            if (Frequency == Frequency.Monthly || (Frequency == Frequency.Yearly && ByMonths.Count > 0))
                return dates.SelectMany(baseDate => AllDaysInMonth(baseDate).Where(d => ByDaysContains(d)));

            if (Frequency == Frequency.Weekly)
                return dates.SelectMany(baseDate => AllDaysInWeek(baseDate).Where(d => ByDaysContains(d)));

            if (Frequency == Frequency.Yearly)
                return dates.SelectMany(baseDate => AllDaysInYear(baseDate).Where(d => ByDaysContains(d)));

            throw new NotImplementedException("ByDay for " + Frequency.ToString());
        }

        bool ByDaysContains(LocalDateTime date)
        {
            // Simple case where there is no Nth occurrence.
            if (ByDays.Any(nth => nth.Occurrence == 0 && date.IsoDayOfWeek == nth.DayOfWeek))
                return true;
            if (ByDays.All(nth => nth.Occurrence == 0))
                return false;

            // Determine period for Nth occurrence
            LocalDateTime[] period;
            switch (Frequency)
            {
                case Frequency.Yearly:
                    if (ByMonths.Count > 0)
                        period = AllDaysInMonth(date).ToArray();
                    else
                        period = AllDaysInYear(date).ToArray();
                    break;
                case Frequency.Monthly:
                    period = AllDaysInMonth(date).ToArray();
                    break;
                default:
                    throw new InvalidOperationException("The nth day occurrence can not be used a frequency of " + Frequency.ToString());
            }

            // Does the date match any nth day?
            foreach (var nth in ByDays)
            {
                if (nth.Occurrence == 0)
                    continue;

                var possibleDays = period.Where(d => d.IsoDayOfWeek == nth.DayOfWeek).ToArray();
                int index = nth.Occurrence > 0
                   ? nth.Occurrence - 1
                   : possibleDays.Length + nth.Occurrence;
                if (0 <= index && index < possibleDays.Length && date == possibleDays[index])
                    return true;
            }

            return false;
        }

        /// <summary>
        ///   All days in a given year.
        /// </summary>
        /// <param name="baseDate">The date containing the year to enumerate.</param>
        /// <returns></returns>
        IEnumerable<LocalDateTime> AllDaysInYear(LocalDateTime baseDate)
        {
            int daysInYear = baseDate.Calendar.GetDaysInYear(baseDate.Year);
            for (int day = 1; day <= daysInYear; ++day)
            {
                yield return baseDate.PlusDays(day - baseDate.DayOfYear);
            }
        }

        /// <summary>
        ///   All days in a given month.
        /// </summary>
        /// <param name="baseDate">The date containing the month to enumerate.</param>
        /// <returns></returns>
        IEnumerable<LocalDateTime> AllDaysInMonth(LocalDateTime baseDate)
        {
            int daysInMonth = baseDate.Calendar.GetDaysInMonth(baseDate.Year, baseDate.Month);
            for (int day = 1; day <= daysInMonth; ++day)
            {
                yield return baseDate.PlusDays(day - baseDate.Day);
            }
        }

        /// <summary>
        ///   All days in a given week.
        /// </summary>
        /// <param name="baseDate">The date containing the week to enumerate.</param>
        /// <returns></returns>
        IEnumerable<LocalDateTime> AllDaysInWeek(LocalDateTime baseDate)
        {
            int offset = 0;
            for (var d = baseDate; WeekStartDay != d.IsoDayOfWeek; d = d.PlusDays(-1))
            {
                --offset;
            }
            for (int day = 0; day < NodaConstants.DaysPerStandardWeek; ++day)
            {
                yield return baseDate.PlusDays(day + offset);
            }
        }

        IEnumerable<int> AbsoluteMonthDays(IEnumerable<int> relativeMonthDays, LocalDateTime baseDate)
        {
            int daysInMonth = baseDate.Calendar.GetDaysInMonth(baseDate.Year, baseDate.Month);
            return relativeMonthDays
                .Select(md => md > 0 ? md : md + daysInMonth + 1)
                .Where(dayInMonth => 1 <= dayInMonth && dayInMonth <= daysInMonth);
        }

        IEnumerable<int> AbsoluteYearDays(IEnumerable<int> relativeYearDays, LocalDateTime baseDate)
        {
            int daysInYear = baseDate.Calendar.GetDaysInYear(baseDate.Year);
            return relativeYearDays
                .Select(yd => yd > 0 ? yd : yd + daysInYear + 1)
                .Where(dayInYear => 1 <= dayInYear && dayInYear <= daysInYear);
        }

        IEnumerable<int> AbsoluteWeeks(IEnumerable<int> relativeWeek, LocalDateTime baseDate)
        {
            int weeksInYear = baseDate.Calendar.GetWeeksInYear(baseDate.Year);
            return relativeWeek
                .Select(rw => rw > 0 ? rw : rw + weeksInYear + 1)
                .Where(week => 1 <= week && week <= weeksInYear);
        }

        IEnumerable<LocalDateTime> LimitBySetPosition(IEnumerable<LocalDateTime> dates)
        {
            if (BySetPositions.Count == 0)
                return dates;

            var set = dates.ToArray();
            return from position in BySetPositions
                   select position > 0
                              ? position - 1
                              : set.Length + position
                   into index where 0 <= index && index < set.Length select set[index];
        }

        IEnumerable<ZonedDateTime> ResolveLocalDateTime(ZoneLocalMapping mapping)
        {
            ZonedDateTime zoned;

            switch (mapping.Count)
            {
                // A strict time (1-1 mapping) is easy.
                case 1:
                    zoned = new ZonedDateTime(mapping.LocalDateTime, mapping.EarlyInterval.WallOffset, mapping.Zone);
//                    Console.WriteLine("{0} => {1}", mapping.LocalDateTime, zoned.ToInstant());
                    yield return zoned;
                    break;

                // An ambiguous time, leaving daylight savings time, returns both possible values.
                case 2: 
                    zoned = new ZonedDateTime(mapping.LocalDateTime, mapping.EarlyInterval.WallOffset, mapping.Zone);
//                    Console.WriteLine("{0} (ambiguous 1) => {1}", mapping.LocalDateTime, zoned.ToInstant());
                    yield return zoned;

                    zoned = new ZonedDateTime(mapping.LocalDateTime, mapping.LateInterval.WallOffset, mapping.Zone);
//                    Console.WriteLine("{0} (ambiguous 2) => {1}", mapping.LocalDateTime, zoned.ToInstant());
                    yield return zoned;
                    break;

                // A skipped time, entering daylight savings time, returns the earliest possible value.
                case 0:
                    var adjustment = mapping.EarlyInterval.LocalStart - mapping.LateInterval.LocalEnd;
                    zoned = new ZonedDateTime(mapping.LocalDateTime.PlusTicks(adjustment.Ticks), mapping.EarlyInterval.WallOffset, mapping.Zone);
//                    Console.WriteLine("{0} (skipped) => {1}", mapping.LocalDateTime, zoned.ToInstant());
                    yield return zoned;
                    break;

                default:
                    throw new InvalidOperationException("Mapping has count outside range 0-2; should not happen.");
            }
        }
            

        /// <summary>
        ///   Filters out any duplicate values.
        /// </summary>
        /// <remarks>
        ///   <b>Assumes</b> that the enumerated items are already ordered.
        /// </remarks>
        IEnumerable<ZonedDateTime> OrderedDistinct(IEnumerable<ZonedDateTime> items)
        {
            ZonedDateTime? last = null;
            foreach (var item in items)
            {
                if (!last.HasValue || item.ToInstant() > last.Value.ToInstant())
                {
                    yield return item;
                    last = item;
                }
            }
        }

        private IEnumerable<ZonedDateTime> PartialSort(IEnumerable<ZonedDateTime> datetimes)
        {
            LocalDate? today = null;
            var todaysInstances = new List<ZonedDateTime>();

            foreach (var datetime in datetimes)
            {
                if (!today.HasValue)
                {
                    today = datetime.LocalDateTime.Date;
                    todaysInstances.Add(datetime);
                }
                else if (today == datetime.LocalDateTime.Date)
                {
                    todaysInstances.Add(datetime);
                }
                else
                {
                    // Sort and yield today's instances.
                    if (todaysInstances.Count == 1)
                    {
                        yield return todaysInstances[0];
                    }
                    else
                    {
                        todaysInstances.Sort();
                        foreach (var sorted in todaysInstances)
                        {
                            yield return sorted;
                        }
                    }

                    // Setup for next today.
                    today = datetime.LocalDateTime.Date;
                    todaysInstances.Clear();
                    todaysInstances.Add(datetime);
                }
            }

            // I think today's instances will always be empty by now.  But just in case.
            if (todaysInstances.Count == 0)
            {
                ;
            }
            else if (todaysInstances.Count == 1)
            {
                yield return todaysInstances[0];
            }
            else
            {
                todaysInstances.Sort();
                foreach (var sorted in todaysInstances)
                {
                    yield return sorted;
                }
            }

        }

    }
}
